#include<bits/stdc++.h>
using namespace std;
class Solution {
public:
    vector<string> fullJustify(vector<string>& words, int maxWidth) {
        int n=words.size();
        int cur=0;
        int count=0;
        queue<string> q;
        vector<string> ret;
        for(int i=0;i<n;i++)
        {
            int l=words[i].size();
            if(maxWidth-(cur+l)>=count)
            {
                q.push(words[i]);
                count++;
                cur+=l;
                if(i==n-1)
                {
                    string s="";
                    while(!q.empty())
                    {
                        s+=q.front();
                        if(q.size()!=1) s+=' '; 
                        q.pop();
                    }
                    while(s.size()!=maxWidth) s+=' ';
                    ret.push_back(s);
                    return ret;
                }
            }
            else
            {
                int average=(maxWidth-cur)/(count-1==0?1:count-1);
                int extra=(maxWidth-cur)%(count-1==0?1:count-1);
                string space="";
                for(int i=0;i<average;i++) space+=' ';
                string s="";
                while(!q.empty())
                {
                    s+=q.front();
                    if(q.size()!=1)
                    { 
                        s+=space;
                        if(extra) 
                        {
                            s+=' ';
                            extra--;
                        }
                    }
                    q.pop();
                }
                ret.push_back(s);
                q.push(words[i]);
                count=1;
                cur=0;cur+=l;
                if(i==n-1)
                {
                    string s="";
                    s+=q.front();
                    q.pop();
                    while(s.size()!=maxWidth) s+=' ';
                    ret.push_back(s);
                }
            }
        }
        return ret;
    }
};

int main()
{
    vector<string> vec={"This", "is", "an", "example", "of", "text", "justification."};
    Solution so;
    for(auto& s:so.fullJustify(vec,16))
    {
        cout<<s<<endl;
    }
    return 0;
}